\section{二 次剩 余}

\begin{frame}{二 次剩 余}


  设整数 $a$ 与 $m$ 互素， 若 $x^{2} \equiv a\left(\mod  m\right)$ 有解， 则称 $a$ 是模 $m$ \emph{二次剩余} (quadratic residue modulo $m$), 否则称为\emph{二次非剩余} (quadratic non-residue).

  \pause
给定正整数 $m$ 后， 求出模 $m$ 二次剩余集并不难：列出小于 $m$ 而又与 $m$ 互素的正整数， 平方之且求模 $m$ 的剩余， 即得到。

\pause
\begin{lemma}%引理1
(1) 设 $a$ 为奇数， $s \geqslant 3$. 则 $a$ 为模 $2^{s}$ 的二次剩余当且仅当
\[
  a \equiv 1 \quad\left(\mod  8\right).
\]
也就是说， $x^{2} \equiv a\left(\mod  2^{s}\right)$ 有解的充分必要条件是
\[
  a \equiv 1 \quad\left(\mod  8\right).
\]

\pause
 (2)  $a$ 为模 $p^{s}$ 的二次剩余 (其中 $s \geqslant 1$, 奇素数 $p \nmid a$) 当且仅当
 \[
   a^{\frac{p-1}{2}} \equiv 1 \quad\left(\mod  p\right).
 \]
 \end{lemma}

\pause
\begin{example}
  (1) 模 $8$ 的二次剩余只有 $1$, 模 $16$ 的二次剩余为 $1$, $9$, 模 $32$ 的二次剩余为 $1,9,17,25$. 

 \pause
 (2) 模 $9$ 的二次剩余 $a$ 满足 $a \equiv 1\left(\mod  3\right)$, 即 $1,4,7$. 

 \pause
 (3) 模 $25$ 的二次剩余 $a$ 满足 $a^{2} \equiv 1\left(\mod  5\right)$, 即 $1,4,6,9,11,14,16,19,21,24$.
 \end{example}
\end{frame}

\begin{frame}
 \begin{proof}
   (1) 
   由\S3.5定理3知 $x^{2} \equiv a\left(\mod  2^{s}\right)$ ($s\geqslant 3$) 有解当且仅当 $x^{2} \equiv a\left(\mod  2^{3}\right)$ 有解。
   又由\S3.5定理1知 $x^{2} \equiv a\left(\mod  2^{3}\right)$ 有解当且仅当 $a \equiv 1\left(\mod  4\right)$且$a \equiv 1\left(\mod  8\right)$. 
   因此$x^{2} \equiv a\left(\mod  2^{s}\right)$ ($s\geqslant 3$) 有解当且仅当$a \equiv 1\left(\mod  8\right)$. 

\pause
  (2) 由 \S3.5 定理 2 知 $x^{2} \equiv a\left(\mod  p^{s}\right)$ 有解当且仅当 $x^{2} \equiv a\left(\mod  p\right)$ 有解。
又由 \S3.4 定理 1 知 $x^{2} \equiv a\left(\mod  p \right)$ 有解当且仅当 
$a^{\frac{p-1}{2}} \equiv 1 \left(\mod  p\right)$. 从而得(2)中断言。
\end{proof}

\pause
  \begin{theorem}%定理1
  设 $m=2^{s} p_{1}^{s_{1}} \cdots p_{t}^{s_{t}}$ 为素因子分解， $(a, m)=1$. 则 $x^{2} \equiv a\left(\mod  m\right)$ 有解当且仅当如下成立：

 (1) 若 $s \geqslant 3$, 则 $a \equiv 1\left(\mod  8\right)$. 若 $s=2$, 则 $a \equiv 1\left(\mod  4\right)$.

 (2) $a^{\left(p_{i}-1\right) / 2} \equiv 1\left(\mod  p_{i}\right)(i=1, \cdots, t)$.
 \end{theorem}

 \begin{proof}
   由 \S3.5 引理 1知$x^{2} \equiv a\left(\mod  m\right)$ 有解当且仅当
   $x^{2} \equiv a\left(\mod  2^s\right)$ 和 $x^{2} \equiv a\left(\mod  p_i^{s_i}\right)$ ($1\leqslant i\leqslant t$) 都有解。
   $s=0$时$a\equiv 0\left( \mod 2^0 \right)$, 方程$x^2\equiv a\left( \mod 2^0 \right)$总有解；
   $s=1$时$a\equiv 1\left( \mod 2 \right)$, $x^{2} \equiv a\left(\mod  2\right)$总有解；
   $s=2$时模$4$的奇数只有$\pm 1$, 其平方都是$1$, 因此$1$是模$4$二次剩余而$-1$不是，这样$x^{2} \equiv a\left(\mod  2^2\right)$当且仅当$a\equiv 1\left( \mod 4 \right)$.
   进而由本节引理 1 可得定理中断言。
\end{proof}

 定理 1 将二次剩余问题归结到模 $p$ (奇素数) 和模 $2^{3}$ 情形。 以下总设 $p$ 为奇素数。
 \end{frame}

 \begin{frame}

 \begin{definition}%定义1
 设 $p$ 为奇素数， Legendre (勒让德) 符号定义如下：
 \[
 \kronecker{a}{p}= \begin{cases}1, & \text { 若~} a \text { 是二次剩余 }\left(\mod  p\right), \\ -1, & \text { 若~} a \text { 是二次非剩余 }\left(\mod  p\right), \\ 0, & \text { 若~} a \equiv 0 \left(\mod  p\right) .\end{cases}
 \]
 \end{definition}

 \pause
 \begin{lemma}%引理2
 (1) (Euler 判则) $\displaystyle\kronecker{a}{p} \equiv a^{\frac{p-1}{2}}\left(\mod  p\right)$.

 (2) $
 \displaystyle
 \kronecker{-1}{p} \equiv(-1)^{\frac{p-1}{2}}=\begin{cases}
   1, & \text { 若~} p \equiv 1 \left(\mod  4\right);  \\
   -1, & \text { 若~} p \equiv 3 \left(\mod  4\right).
 \end{cases}
 $\\
 也就是说，$-1\left( \mod p \right)$有平方根当且仅当$p\equiv 1\left( \mod 4 \right)$. 
 实际上，当 $p \equiv 1\left(\mod  4\right)$ 时， $\left(\kronecker{p-1}{2}!\right)^{2} \equiv-1 \left(\mod  p\right)$.
 \end{lemma}

 \pause
 \begin{example}
   (1) $6$为模$31$二次非剩余，因为
   \(
     \kronecker{6}{31} \equiv 6^{15}\equiv -1\left( \mod 31 \right).
   \)

   (2) $-1$模$59$无平方根。
 \end{example}
 \end{frame}

 \begin{frame}

\pause
 \begin{proof}
   (1) $p\mid a$时两边都等于$0$, 故相等。令$p\nmid a$. 有
   \(
     \left(  a^{\frac{p-1}{2}} \right)^2 =a^{p-1}\equiv 1\left( \mod p \right).
   \)
   而$x^2\equiv 1\left( \mod p \right)$恰好有两个根$\pm 1$.
  因此 $a^{\frac{p-1}{2}} \equiv \pm 1 \left(\mod  p\right)$.
 进而由引理 1(2) 即得 Euler判则。

 \pause
 (2)在 (1) 中令 $a=-1$即得。 再由Wilson 定理  
 \(
   (p-1)!\equiv -1\left( \mod p \right)
 \)
 知
 \[
   (-1)^{\frac{p-1}{2}}((\frac{p-1}{2})!)^2\equiv -1\left( \mod p \right).
 \]
 故
$p \equiv 1\left(\mod  4\right)$ 时， 
\(
  \left(\kronecker{p-1}{2}!\right)^{2} \equiv-1 \left(\mod  p\right).
\)
 \end{proof}

 \pause
 \begin{corollary}%系1
   (1) $\displaystyle\kronecker{a b}{p}=\kronecker{a}{p}\kronecker{b}{p}$.

  (2) 若 $a \equiv b\left(\mod  p\right)$, 则 $\displaystyle\kronecker{a}{p}=\kronecker{b}{p}$.

(3) 模 $p$ 的二次剩余和非剩余个数相等， 均为 $\frac{p-1}{2}$. 模 $p$ 的二次剩余恰为
\(
  1^{2},  2^{2},   3^{2},   \cdots,  \kronecker{p-1}{2}^{2}.
\)

(4) 模 $p$ 的两个二次剩余之积仍为二次剩余。 两个非剩余之积为剩余。 剩余与非剩余之积为非剩余。
\end{corollary}
 \end{frame}

 \begin{frame}
\begin{proof}
  (1) 由引理 1(1) 得
\[
  \kronecker{a b}{p} \equiv(a b)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}} b^{\frac{p-1}{2}} \equiv\kronecker{a}{p}\kronecker{b}{p} \quad\left(\mod  p\right).
\]

 (2) 由二次剩余和Legendre符号的定义即知。

 (3) 注意到在$\FF_p$上有分解
 \[
   x^{p-1}-1 = (x-1) \cdots\left(x-(p-1)\right).
 \]
 而$(x^{\frac{p-1}{2}}-1) \mid (x^{p-1}-1)$,
 因此多项式$x^{\frac{p-1}{2}}-1\in \FF_p[x]$能分裂为$\frac{p-1}{2}$个不同的首一一次因子的乘积。
 这样 $a^{\frac{p-1}{2}} \equiv 1\left(\mod  p\right)$ 有 $\frac{p-1}{2}$ 个解，故有 $\frac{p-1}{2}$ 个二次剩余；其余是二次非剩余。
 注意到$1\leqslant i\neq j\leqslant \frac{p-1}{2}$时$i^2\nequiv j^2\left( \mod p \right)$,
 因此
   $1,  2^2,  \cdots,  \left( \frac{p-1}{2}\right)^2$
 为$\frac{p-1}{2}$个互异的二次剩余。
这正是所有的二次剩余。

(4) 由(1)这是显然的。
 \end{proof}

 \pause
  \begin{lemma}%引理3
     [Gauss 引理]
     \label{Gauss引理}
     设奇素数 $p \nmid a, \nu$ 是 $\{a, 2 a, \cdots, \frac{p-1}{2}a\}$ 的模 $p$最小正剩余中的大于$\frac{p}{2}$的个数（亦即绝对最小剩余中负数的个数）， 则
    \[
      \kronecker{a}{p}=(-1)^{\nu}.
\]
\end{lemma}
 \end{frame}

 \begin{frame}
\pause
\begin{example}
  $p=11$ 时， $\frac{p-1}{2}=5$. 
\pause
  对 $a=2$, 
  \[
    \{2,2 \cdot 2,3 \cdot 2,4 \cdot 2, 5 \cdot 2\}= \{2,4,6,8,10\}\left( \mod 11 \right),
  \]
  故 $\nu=3$, $\kronecker{2}{ 11}=-1$. 
\pause
  而对 $a=3$, 
  \[
    \{3,2 \cdot 3,3 \cdot 3,4 \cdot 3,5 \cdot 3\}\equiv \left\{ 3,6,9,1,4 \right\}\left( \mod 11 \right),
  \]
  故 $\nu= 2$, $\kronecker{3}{11}=1$. 事实上， $5^{2} \equiv 3\left(\mod  11\right)$.
 \end{example}

 \pause
  \begin{lemma}%引理4
    \label{(2/p)的公式}
    $\displaystyle\kronecker{2}{p}=(-1)^{\frac{ p^{2}-1}{ 8}}=
  \begin{cases}
    1, & \text { 若~} p \equiv \pm 1 \left(\mod  8\right), \\
  -1, & \text { 若~} p \equiv \pm 3 \left(\mod  8\right) .
\end{cases}$
\end{lemma}

\pause
\begin{example}
$p=7,17,23,31$ 时， $2$ 为二次剩余。实际上，
\[
  3^{2} \equiv 2 \left(\mod  7\right),\quad  6^{2} \equiv 2 \left(\mod  17\right),\quad  5^{2} \equiv 2 \left(\mod  23\right),\quad  8^{2} \equiv 2 \left(\mod  31\right).
\]
\pause
  而 $p=3,5,11,13$ 时， $2$ 为二次非剩余。
\end{example}
 \end{frame}

 \begin{frame}
   \begin{example}
     用引理 4 可证明： 有无限多 $8 k-1$ 型素数 $(k \in \mathbb{Z})$. 
\pause
事实上， 设 $p_{1}, \cdots, p_{t}$为这种素数， 令 $M=\left(4 p_{1} \cdots p_{t}\right)^{2}-2$, 则 $M$ 的奇素数因子 $p$ 只能是 $8 k \pm 1$ 型， 因为 $2\equiv (4p_1\cdots p_t)^2$ 是模 $p$ 的二次剩余。 但 $M$ 的奇素因子不能都是 $8 k+1$ 型， 因为这种因子之积仍为 $8 k+1$ 型， 而 $M=2(8 k-1)$. 故 $M$ 必有奇素因子 $p$ 为 $8 k-1$ 型， 且不等于 $p_{1}, \cdots, p_{t}$.
   \end{example}

   \pause

   \begin{proof*}[Gauss 引理的证明]
 记
 \[
   \{a, 2 a, \cdots, \frac{p-1}{2}a \} \equiv\left\{ \pm s_{1}, \pm s_{2}, \cdots, \pm s_{\frac{p-1}{2}}\right\} \quad\left(\mod  p\right),
 \]
 其中 $0<s_{k} \leqslant\frac{p-1}{2}$; 即 $\pm s_{k}$ 为 $k a$ 模 $p$ 绝对最小剩余。
 \pause
 可断言 $s_{k} \neq s_{j}$ ($1 \leqslant k \neq j \leqslant\frac{p-1}{2}$); 事实上， 若 $k a \equiv \pm j a\left(\mod  p\right)$, 则 $k \mp j \equiv 0\left(\mod  p\right)$, 矛盾。
\pause
 这说明
 \[
   \left\{s_{1}, s_{2}, \cdots, s_{\frac{p-1}{2}}\right\}=\{1,2, \cdots,\frac{p-1}{2}\}.
 \]
 \pause
 对证明开始的等式， 两边求其元素乘积得
 \[
     a^{\frac{p-1}{2}} \cdot[\frac{p-1}{2}]!\equiv(-1)^{\nu} s_{1} \cdots s_{\frac{p-1}{2}}=(-1)^{\nu}[\frac{p-1}{2}]!\quad\left(\mod  p\right).
   \]
   从而
  \[
    \kronecker{a}{p}\equiv a^{\frac{p-1}{2}}\equiv  (-1)^{\nu} \quad\left(\mod  p\right).
 \]
 \end{proof*}
 
 \end{frame}

 \begin{frame}
   \begin{proof*}[引理~\ref{(2/p)的公式}~的证明]
     用引理 3, $\kronecker{2}{p}=(-1)^{\nu}$. 
     Gauss引理要求我们找到 $\left\{2 \cdot 1,2 \cdot 2, \cdots, 2 \cdot \frac{p-1}{2}\right\}$中
     模$p$最小正剩余中大于$\frac{p}{2}$的整数的个数$\nu$, 显然$\nu$就是该集合中大于 $\frac{p-1}{2}$ 的个数。
     \pause
     注意到对整数$k$,
 \[
   \frac{p-1}{2}<2 \cdot k \leqslant 2 \cdot \frac{p-1}{2} \quad \Leftrightarrow \quad \frac{p-1}{4}<k \leqslant \frac{p-1}{2} \quad \Leftrightarrow \quad \rho<k \leqslant \frac{p-1}{2},
 \]
 其中$\rho=[\frac{p-1}{4}]$ (整数部分).
故 $\nu=\frac{p-1}{2}-\rho$. 
\pause
当 $p=8 k+1,8 k+3,8 k+5,8 k+7$ 时， 依次有
 \[
 \begin{aligned}
    \frac{p-1}{2}&= 4 k, 4 k+1,4 k+2,4 k+3,\\
    \rho&= 2 k, 2 k, 2 k+1,2 k+1,
\end{aligned}
 \]
故
 \[
   \nu=\frac{p-1}{2}-\rho=2 k, 2 k+1,2 k+1,2 k+2.
 \]
 \pause
 由 Gauss 引理知依次有 
 \[
   \kronecker{2}{p}=(-1)^{\nu}=1,-1,-1,1,
 \]
 即得引理。
 \end{proof*}

 \pause

\end{frame}


\begin{frame}{小结}
  \begin{enumerate}
    \item 说说奇数为模$2^s$ ($s\geqslant 3$)二次剩余的条件。
      说说与奇素数$p$互素的数为模$p^s$二次剩余的条件。(叙述引理1)
    \item 说说与$m$互素的数为模$m$二次剩余的条件。(叙述定理1)
    \item Legendre符号含义如何？
    \item Euler判别法告诉我们如何算Legendre符号？Gauss引理告诉我们如何算Legendre符号？
    \item $-1$何时为模$p$二次剩余？$2$何时为模$p$二次剩余？
    \item 说说Legendre符号的一些性质。二次剩余与非剩余的个数有何关系？
    \item $p\left( \mod 4 \right)$等于几时$-1\left( \mod p \right)$一定有平方根？
      指出一个这样的平方根。
    \item $p\left( \mod 4 \right)=3$时二次剩余$a$的平方根为？
      $p\left( \mod 8 \right)=5$时二次剩余$a$的平方根为？
  \end{enumerate}
\end{frame}
